"""
https://leetcode.cn/problems/daily-temperatures/description/

739. 每日温度
已解答
中等
相关标签
相关企业
提示
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

 

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]
 

提示：

1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

"""

from typing import List


class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        """
        此题直接考虑，则是对每一天，往下轮询m天，计算下一次更高的天数。
        浪费的算力在于，如果a>b,b>c,则a>c
        可以使用一个元组，分别存储天数和对应温度。
        同时用一个栈，存储这个元组集合。栈的排序则是，越在底部，温度越高；温度相同的情况，天数越靠前，则越靠近底部。

        构建方式：
        第一天自然是直接将天数和温度推入栈中。
        接下来，轮询到第m天时，如果温度小于等于栈顶的温度，则将第m天的信息元素推入栈中；
        否则，持续将栈pop，并在对应天数上，记录m与pop元素的天数之差，直到栈清空或某个栈顶元素的温度大于等于第m天温度；这时再将信息push到栈中。
        遍历到最后一天后，持续将所有栈pop出，并在对应天数的结果上记录0。

        由于每一个元素信息，都记录在了栈中，所以可以保证每天都有结果信息。

        """
        res_list=[0]*len(temperatures)
        sta=[]

        for (i,temp) in enumerate(temperatures):  
            while sta and temperatures[sta[-1]]<temp:
                old_i=sta.pop()
                res_list[old_i]=i-old_i
            sta.append(i)

        return res_list
    
if __name__ =='__main__':
    sol=Solution()
    temps=[73,74,75,71,69,72,76,73]
    res_list=sol.dailyTemperatures(temps)
    print(res_list)
